package algorithm;

public class NextPermutation {
    public void nextPermutation(int[] nums) {
        // 长度大于等于2
        int i = nums.length - 2;
        // 从右往左找到，（左小，右大）组合
        while (i >= 0 && nums[i] >= nums [i+1]) {
            i--;
        }
        if (i >= 0) {
            // 此时 i+1 到 nums.length - 1 是递减的
            // 从右往左找到第一个比i大的数
            int j = nums.length - 1;
            while (j > 0 && nums[i] >= nums[j]) {
                j--;
            }
            swap(nums, i ,j);
        }
        //反转i+1 到nums.length -1
        reverse(nums, i+1);
    }

    public void reverse(int[] nums, int start) {
        int left = start, right = nums.length - 1;
        while (left < right) {
            swap(nums, left, right);
            left++;
            right--;
        }
    }

    public void swap(int[] nums, int i, int j) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }
}
